﻿#pragma once

#include <functional>
#include <iostream>
#include <vector>

namespace xi
{

namespace stl
{

namespace details
{

// ANSI 转义码
inline auto ansiRed = "\x1b[31m";
inline auto ansiGray = "\x1b[90m";
inline auto ansiReset = "\x1b[0m";

// 颜色枚举
enum class RB_Color
{
    Black,
    Red,
};

template <class T, typename Data> struct Tree_Node
{
    T value{};                                        // 节点值
    Data data{};                                      // 节点数据
    Tree_Node *_parent{nullptr};                      // 父节点
    std::vector<Tree_Node *> nodes{nullptr, nullptr}; // 子节点

    /**
     * @brief 获得父节点
     *
     * @return Tree_Node*&
     */
    Tree_Node *&parent() noexcept
    {
        return _parent;
    }

    /**
     * @brief 获得左子节点
     *
     * @return Tree_Node*&
     */
    Tree_Node *&lc() noexcept
    {
        return nodes[0];
    }

    /**
     * @brief 获得 i 号右子节点
     *
     * @param[in] i
     * @return Tree_Node*&
     */
    Tree_Node *&rc(std::size_t i = 0) noexcept
    {
        return nodes[1 + i];
    }
};

template <class T> struct Tree_Node<T, void>
{
    T value{};                                        // 节点值
    Tree_Node *_parent{nullptr};                      // 父节点
    std::vector<Tree_Node *> nodes{nullptr, nullptr}; // 子节点

    /**
     * @brief 获得父节点
     *
     * @return Tree_Node*&
     */
    Tree_Node *&parent() noexcept
    {
        return _parent;
    }

    /**
     * @brief 获得左子节点
     *
     * @return Tree_Node*&
     */
    Tree_Node *&lc() noexcept
    {
        return nodes[0];
    }

    /**
     * @brief 获得 i 号右子节点
     *
     * @param[in] i
     * @return Tree_Node*&
     */
    Tree_Node *&rc(std::size_t i = 0) noexcept
    {
        return nodes[1 + i];
    }
};

} // namespace details

template <class T, typename Compare = std::less<T>, typename Data = void, bool Destructible = true> class Tree
{
    using Node = details::Tree_Node<T, Data>;

  protected:
    Compare cmp{};            // 比较函数
    Node *m_nil = new Node{}; // 根节点的父节点是 nil，nil 没有特定的父节点和子节点
    Node *m_root = m_nil;     // 根节点，整棵树的起始节点

  public:
    Tree(Tree &&) = delete;

    /**
     * @brief 默认构造
     *
     */
    Tree() = default;

    /**
     * @brief 默认析构函数，如果 Destructible 为 false，则认为 Tree 所在类的析构函数会销毁所有节点，不需要 Tree
     * 自己析构
     *
     */
    virtual ~Tree()
    {
        if (Destructible)
            postorder_walk(m_root, [](Node *node) { delete node; });
        delete m_nil;
    }

    /**
     * @brief 获得树的规模
     *
     * @return std::size_t
     */
    constexpr std::size_t size() const noexcept
    {
        return m_root->size();
    }

    /**
     * @brief 获得空
     *
     * @return Node*
     */
    constexpr Node *nil() const noexcept
    {
        return m_nil;
    }

    /**
     * @brief 获得根节点
     *
     * @return constexpr Node*
     */
    constexpr Node *root() const noexcept
    {
        return this->m_root;
    }

    /**
     * @brief 节点查找
     *
     * @param[in] value
     * @return Node*
     */
    virtual Node *find(const T &value) const = 0;

    /**
     * @brief 插入值
     *
     * @param[in] value
     * @return Node*
     */
    virtual Node *insert(const T &value) = 0;

    /**
     * @brief 移除值
     *
     * @param[in] value
     * @return true
     * @return false
     */
    virtual bool remove(const T &value) = 0;

    /**
     * @brief 根据节点删除
     *
     * @param[in] p
     * @return true
     * @return false
     */
    virtual bool remove(Node *p) = 0;

    /**
     * @brief 后序遍历
     *
     * @tparam Func
     * @param[in] node
     * @param[in] func
     */
    template <typename Func> void postorder_walk(Node *node, Func &&func)
    {
        if (node != m_nil)
        {
            for (auto child : node->nodes)
                postorder_walk(child, func);
            func(node);
        }
    }

    /**
     * @brief 中序遍历
     *
     * @tparam Func
     * @param[in] node
     * @param[in] func
     */
    template <typename Func> void inorder_walk(Node *node, Func &&func)
    {
        if (node != m_nil)
        {
            // 先输出左子树，再输出当前节点，最后输出右子树
            inorder_walk(node->lc(), func);
            func(node);
            inorder_walk(node->rc(), func);
        }
    }

    /**
     * @brief 前序遍历
     *
     * @tparam Func
     * @param[in] node
     * @param[in] func
     */
    template <typename Func> void preorder_walk(Node *node, Func &&func)
    {
        if (node != m_nil)
        {
            func(node);
            for (auto child : node->nodes)
                preorder_walk(child, func);
        }
    }

    /**
     * @brief 后序遍历
     *
     * @tparam Func
     * @param[in] node
     * @param[in] func
     */
    template <typename Func> void postorder_walk(Node *node, Func &&func) const
    {
        if (node != m_nil)
        {
            for (auto child : node->nodes)
                postorder_walk(child, func);
            func(node);
        }
    }

    /**
     * @brief 中序遍历
     *
     * @tparam Func
     * @param[in] node
     * @param[in] func
     */
    template <typename Func> void inorder_walk(Node *node, Func &&func) const
    {
        if (node != m_nil)
        {
            // 先输出左子树，再输出当前节点，最后输出右子树
            inorder_walk(node->lc(), func);
            func(node);
            inorder_walk(node->rc(), func);
        }
    }

    /**
     * @brief 前序遍历
     *
     * @tparam Func
     * @param[in] node
     * @param[in] func
     */
    template <typename Func> void preorder_walk(Node *node, Func &&func) const
    {
        if (node != m_nil)
        {
            func(node);
            for (auto child : node->nodes)
                preorder_walk(child, func);
        }
    }
};

template <class T, bool Destructible = true> class MN_Tree : public Tree<T, std::less<T>, void, Destructible>
{
  public:
    using Node = details::Tree_Node<T, void>;

    MN_Tree(MN_Tree &&) = delete;

    /**
     * @brief 默认构造
     *
     */
    MN_Tree() : Tree<T, std::less<T>, void, Destructible>()
    {
        // 必须清除子节点
        this->m_nil->nodes.clear();
    }

    /**
     * @brief 插入新值
     *
     * @param[in] value
     * @param[in] parent
     * @return Node*
     */
    Node *insert(const T &value, Node *parent)
    {
        // 创建新节点
        Node *node = new Node;
        node->value = value;
        node->nodes.clear();

        if (this->m_root == this->m_nil)
        {
            this->m_root = node;
            this->m_root->parent() = this->m_nil;
            return this->m_root;
        }

        if (parent == nullptr || parent == this->m_nil)
            parent = this->m_root;

        parent->nodes.push_back(node);
        node->parent() = parent;
        return node;
    }

    /**
     * @brief 节点查找
     *
     * @param[in] value
     * @return Node*
     */
    Node *find(const T &value) const override
    {
        Node *p = this->m_nil;
        auto func = [&](Node *node) {
            if (node->value == value)
                p = node;
        };

        this->preorder_walk(this->m_root, func);
        return p;
    }

    /**
     * @brief 插入值
     *
     * @param[in] value
     * @return Node*
     */
    Node *insert(const T &value) override
    {
        return insert(value, this->m_nil);
    }

    /**
     * @brief 移除值
     *
     * @param[in] value
     * @return true
     * @return false
     */
    bool remove(const T &value) override
    {
        // 找到节点
        Node *p = find(value);
        return remove(p);
    }

    /**
     * @brief 根据节点删除
     *
     * @param[in] p
     * @return true
     * @return false
     */
    bool remove(Node *p) override
    {
        if (p == nullptr || p == this->m_nil)
            return false;

        Node *node = p;
        auto parent = node->parent();
        if (node == this->m_root)
        {
            this->m_root = this->m_nil;

            // 如果还有子节点，就用第一个子节点代替根节点
            if (!node->nodes.empty())
            {
                auto front = node->nodes.front();
                node->nodes.erase(node->nodes.begin());
                this->m_root = front;
                front->parent() = this->m_nil;
                parent = this->m_root;
            }
        }

        // 注意这里 parent 可能是 node 的子节点，无法查找到 node
        auto it = std::find(parent->nodes.begin(), parent->nodes.end(), node);
        if (it != parent->nodes.end())
            parent->nodes.erase(it);

        // 修改连接关系
        for (auto child : node->nodes)
        {
            parent->nodes.push_back(child);
            child->parent() = parent;
        }
        delete node;
        return true;
    }
};

template <class T, typename Compare = std::less<T>, typename Data = void>
class Binary_Tree : public Tree<T, Compare, Data, true>
{
  public:
    using Node = details::Tree_Node<T, Data>;

    Binary_Tree(Binary_Tree &&) = delete;

    /**
     * @brief 默认构造
     *
     */
    Binary_Tree() = default;

    struct Iterator
    {
        Node *nil;
        Node *p;

        /**
         * @brief 自增运算符
         *
         * @return Iterator&
         */
        Iterator &operator++()
        {
            // 如果有右节点，就返回右边最小的节点
            if (p->rc() != nil)
            {
                p = p->rc();
                while (p->lc() != nil)
                    p = p->lc();
                return *this;
            }

            // 否则就向上查找，直到 pos==nil 或者 pos 从左边返回
            Node *pos = p->parent();
            while (pos != nil && pos->lc() != p)
            {
                p = pos;
                pos = p->parent();
            }
            p = pos;
            return *this;
        }

        /**
         * @brief 前置自增运算符
         *
         * @return Iterator&
         */
        Iterator &operator++(int)
        {
            ++(*this);
            return *this;
        }

        /**
         * @brief 指定步长的前置自增运算符
         *
         * @param[in] n
         * @return Iterator&
         */
        Iterator &operator+(std::size_t n)
        {
            while (n-- > 0)
                ++(*this);
            return *this;
        }

        /**
         * @brief 自减运算符
         *
         * @return Iterator&
         */
        Iterator &operator--()
        {
            // 如果有左节点，就返回左边最大的节点
            if (p->lc() != nil)
            {
                p = p->lc();
                while (p->rc() != nil)
                    p = p->rc();
                return *this;
            }

            // 否则就向上查找，直到 pos==nil 或者 pos 从右边返回
            Node *pos = p->parent();
            while (pos != nil && pos->rc() != p)
            {
                p = pos;
                pos = p->parent();
            }
            p = pos;
            return *this;
        }

        /**
         * @brief 前置自减运算符
         *
         * @return Iterator&
         */
        Iterator &operator--(int)
        {
            --(*this);
            return *this;
        }

        /**
         * @brief 指定步长的前置自减运算符
         *
         * @param[in] n
         * @return Iterator&
         */
        Iterator &operator-(std::size_t n)
        {
            while (n-- > 0)
                --(*this);
            return *this;
        }

        /**
         * @brief 比较运算符
         *
         * @param[in] other
         * @return true
         * @return false
         */
        bool operator==(const Iterator &other) const
        {
            return p == other.p;
        }

        /**
         * @brief 不等运算符
         *
         * @param[in] other
         * @return true
         * @return false
         */
        bool operator!=(const Iterator &other) const
        {
            return p != other.p;
        }

        /**
         * @brief 取值运算符
         *
         * @return T&
         */
        T &operator*() const
        {
            return p->value;
        }
    };

    /**
     * @brief 获得迭代器
     *
     * @return Iterator
     */
    Iterator begin() const
    {
        return Iterator{this->m_nil, min(this->m_root)};
    }

    /**
     * @brief 终止迭代器
     *
     * @return Iterator
     */
    Iterator end() const
    {
        return Iterator{this->m_nil, this->m_nil};
    }

    /**
     * @brief 节点查找
     *
     * @param[in] value
     * @return Node*
     */
    Node *find(const T &value) const override
    {
        Node *p = this->m_root;
        while (p != this->m_nil)
        {
            if (this->cmp(p->value, value))
                p = p->rc();
            else if (this->cmp(value, p->value))
                p = p->lc();
            else
                break;
        }
        return p;
    }

    /**
     * @brief 插入值
     *
     * @param[in] value
     * @return Node*
     */
    Node *insert(const T &value) override
    {
        // 创建新节点
        if (this->m_root == this->m_nil)
        {
            this->m_root = new Node;
            this->m_root->value = value;
            this->m_root->parent() = this->m_nil;
            this->m_root->lc() = this->m_nil;
            this->m_root->rc() = this->m_nil;
            return this->m_root;
        }

        // 否则从根节点出发向下，利用比较确定向左还是向右，沿途的节点 size 都加 1
        Node *p = this->m_root;
        Node *pos = this->m_nil; // 记录最终插入位置
        while (true)
        {
            // 向左，遇到叶节点就创建新节点，然后退出循环
            if (this->cmp(value, p->value))
            {
                if (p->lc() != this->m_nil)
                    p = p->lc();
                else
                {
                    p->lc() = new Node;
                    pos = p->lc();
                    break;
                }
            }
            // 向右，遇到叶节点就创建新节点，然后退出循环
            else
            {
                if (p->rc() != this->m_nil)
                    p = p->rc();
                else
                {
                    p->rc() = new Node;
                    pos = p->rc();
                    break;
                }
            }
        }

        // 插入点赋值
        pos->value = value;
        pos->parent() = p;
        pos->rc() = this->m_nil;
        pos->lc() = this->m_nil;
        return p;
    }

    /**
     * @brief 移除值
     *
     * @param[in] value
     * @return true
     * @return false
     */
    bool remove(const T &value) override
    {
        // 找到节点
        Node *p = find(value);
        return remove(p);
    }

    /**
     * @brief 根据节点删除
     *
     * @param[in] p
     * @return true
     * @return false
     */
    bool remove(Node *p) override
    {
        if (p == nullptr || p == this->m_nil)
            return false;

        Node *q = p->parent();
        Node *lp = p->lc();
        Node *rp = p->rc();

        if (rp == this->m_nil)
        {
            // 最简单的情况，直接连接
            if (q->lc() == p)
                q->lc() = lp;
            else
                q->rc() = lp;
            lp->parent() = q;

            // 如果删除了根，重设根
            if (p == this->m_root)
                this->m_root = lp;
            delete p;
        }
        else
        {
            // 有右子树，则选择最小节点
            Node *node = min(rp);

            // 如果最小节点不是 rp，则将它移动到 rp 位置
            if (node != rp)
            {
                node->parent()->lc() = node->rc();
                node->rc()->parent() = node->parent();

                p->rc() = node;
                node->parent() = p;
                node->rc() = rp;
                rp->parent() = node;
            }

            // 连接 q 和 node
            lp->parent() = node;
            node->parent() = q;
            node->lc() = lp;
            if (q->lc() == p)
                q->lc() = node;
            else
                q->rc() = node;

            // 如果删除了根，重设根
            if (p == this->m_root)
                this->m_root = node;
            delete p;
        }
        return true;
    }

    /**
     * @brief 获得最大节点
     *
     * @param[in] p
     * @return Node*
     */
    Node *max(Node *p = nullptr) const
    {
        if (p == nullptr)
            p = this->m_root;
        if (p == this->m_nil)
            return this->m_nil;
        while (p->rc() != this->m_nil)
            p = p->rc();
        return p;
    }

    /**
     * @brief 获得最小节点
     *
     * @param[in] p
     * @return Node*
     */
    Node *min(Node *p = nullptr) const
    {
        if (p == nullptr)
            p = this->m_root;
        if (p == this->m_nil)
            return this->m_nil;
        while (p->lc() != this->m_nil)
            p = p->lc();
        return p;
    }
};

template <class T>
class Interval_Tree
    : public Binary_Tree<std::tuple<T, T>, std::function<bool(const std::tuple<T, T> &, const std::tuple<T, T> &)>, T>
{
  public:
    using Node = details::Tree_Node<std::tuple<T, T>, T>;

    Interval_Tree(Interval_Tree &&) = delete;

    /**
     * @brief 默认构造
     *
     */
    Interval_Tree()
        : Binary_Tree<std::tuple<T, T>, std::function<bool(const std::tuple<T, T> &, const std::tuple<T, T> &)>, T>()
    {
        // 指定比较函数
        this->cmp = [](const std::tuple<double, double> &a, const std::tuple<double, double> &b) {
            return std::get<0>(a) < std::get<0>(b);
        };
    }

    /**
     * @brief 插入值
     *
     * @param[in] value
     * @return Node *
     */
    Node *insert(const std::tuple<T, T> &value) override
    {
        // 创建新节点
        if (this->m_root == this->m_nil)
        {
            this->m_root = new Node;
            this->m_root->value = value;
            this->m_root->parent() = this->m_nil;
            this->m_root->lc() = this->m_nil;
            this->m_root->rc() = this->m_nil;
            this->m_root->data = std::get<1>(value);

            // nil 记录最小值
            this->m_nil->data = std::get<0>(value);
            return this->m_root;
        }

        // 否则从根节点出发向下，利用比较确定向左还是向右，沿途的节点 size 都加 1
        Node *p = this->m_root;
        Node *pos = this->m_nil;
        while (true)
        {
            p->data = std::max(p->data, std::get<1>(value));

            // 向左，遇到叶节点就创建新节点，然后退出循环
            if (this->cmp(value, p->value))
            {
                if (p->lc() != this->m_nil)
                    p = p->lc();
                else
                {
                    p->lc() = new Node;
                    pos = p->lc();
                    break;
                }
            }
            // 向右，遇到叶节点就创建新节点，然后退出循环
            else
            {
                if (p->rc() != this->m_nil)
                    p = p->rc();
                else
                {
                    p->rc() = new Node;
                    pos = p->rc();
                    break;
                }
            }
        }

        // 插入点赋值
        pos->value = value;
        pos->parent() = p;
        pos->rc() = this->m_nil;
        pos->lc() = this->m_nil;
        pos->data = std::get<1>(value);

        // nil 记录最小值
        this->m_nil->data = std::min(this->m_nil->data, std::get<0>(value));
        return p;
    }

    /**
     * @brief 根据值删除
     *
     * @param[in] value
     * @return true
     * @return false
     */
    bool remove(const std::tuple<T, T> &value) override
    {
        // 找到节点
        Node *p = this->find(value);
        return remove(p);
    }

    /**
     * @brief 根据节点删除
     *
     * @param[in] p
     * @return true
     * @return false
     */
    bool remove(Node *p) override
    {
        if (p == nullptr || p == this->m_nil)
            return false;

        Node *q = p->parent();
        Node *lp = p->lc();
        Node *rp = p->rc();

        // 调整节点规模，从 tail 一路向上，直到 head 为止，减少路径上节点的 size
        auto reduce = [](Node *head, Node *tail) {
            // 收尾相同，直接退出
            if (head == tail)
                return;

            Node *base = tail;
            T max = std::max(base->rc()->data, base->lc()->data);

            // 先处理以 tail 为子节点的节点
            tail = tail->parent();
            if (base == tail->lc())
                tail->data = std::max(max, std::max(tail->rc()->data, std::get<1>(tail->value)));
            else
                tail->data = std::max(max, std::max(tail->lc()->data, std::get<1>(tail->value)));

            // 处理更高级的节点
            while (tail != head)
            {
                tail = tail->parent();
                tail->data = std::max(tail->rc()->data, std::max(tail->lc()->data, std::get<1>(tail->value)));
            }
        };

        reduce(this->m_root, p);
        if (rp == this->m_nil)
        {
            // 最简单的情况，直接连接
            if (q->lc() == p)
                q->lc() = lp;
            else
                q->rc() = lp;
            lp->parent() = q;

            // 如果删除了根，重设根
            if (p == this->m_root)
                this->m_root = lp;
            delete p;
        }
        else
        {
            // 有右子树，则选择最小节点
            Node *node = this->min(rp);
            reduce(rp, node);

            // 如果最小节点不是 rp，则将它移动到 rp 位置
            if (node != rp)
            {
                node->parent()->lc() = node->rc();
                node->rc()->parent() = node->parent();

                p->rc() = node;
                node->parent() = p;
                node->data = std::max(rp->data, std::get<1>(node->value));
                node->rc() = rp;
                rp->parent() = node;
            }

            // 连接 q 和 node
            lp->parent() = node;
            node->parent() = q;
            node->lc() = lp;
            node->data = std::max(lp->data, node->data);
            if (q->lc() == p)
                q->lc() = node;
            else
                q->rc() = node;

            // 如果删除了根，重设根
            if (p == this->m_root)
                this->m_root = node;
            delete p;
        }
        return true;
    }

    /**
     * @brief 从 r 节点开始查找重叠区间
     *
     * @param[in] value
     * @param[in] r
     * @return Node *
     */
    Node *overlap(const std::tuple<T, T> &value, Node *r = nullptr)
    {
        // 如果起始位置的最大区间比 value 的最小值还小，则放弃搜索
        Node *p = r == nullptr ? this->m_root : r;
        if (p == this->m_nil || p->data < std::get<0>(value))
            return this->m_nil;

        // 判断是否重叠，重叠则返回
        if (std::get<0>(p->value) < std::get<0>(value) && std::get<1>(p->value) > std::get<0>(value))
            return p;
        if (std::get<0>(p->value) < std::get<1>(value) && std::get<1>(p->value) > std::get<1>(value))
            return p;
        if (std::get<0>(value) < std::get<1>(p->value) && std::get<1>(value) > std::get<1>(p->value))
            return p;
        if (std::get<0>(value) < std::get<1>(p->value) && std::get<1>(value) > std::get<1>(p->value))
            return p;

        // 查找左右子树，左树没找到则找右树
        r = overlap(value, p->lc());
        if (r == this->m_nil)
            r = overlap(value, p->rc());
        return r;
    }
};

template <class T, typename Compare = std::less<T>> class RB_Tree : public Binary_Tree<T, Compare, details::RB_Color>
{
    using Color = details::RB_Color;

  public:
    using Node = details::Tree_Node<T, Color>;

    RB_Tree(RB_Tree &&) = delete;

    /**
     * @brief 默认构造
     *
     */
    RB_Tree() : Binary_Tree<T, Compare, Color>()
    {
        // 这里必须显式设置，枚举类型默认为第一个值
        this->m_nil->data = Color::Black;
    }

    /**
     * @brief 高度查询
     *
     * @param[in] node
     * @return std::size_t
     */
    std::size_t height(Node *node = nullptr) const
    {
        // 默认设为根节点
        if (node == nullptr)
            node = this->m_root;

        // 高度是左右子树中最高的高度 +1
        if (node != this->m_nil)
            return std::max(height(node->lc()), height(node->rc())) + 1;
        return 0;
    }

    /**
     * @brief 黑高度查询
     *
     * @param[in] node
     * @return std::size_t
     */
    std::size_t black_height(Node *node = nullptr) const
    {
        // 默认设为根节点
        if (node == nullptr)
            node = this->m_root;

        if (node != this->m_nil)
        {
            std::size_t h = std::max(black_height(node->lc()), black_height(node->rc()));
            if (node->data == Color::Black)
                h++;
            return h;
        }
        return 0;
    }

    /**
     * @brief 节点插入和删除算法
     *
     * @param[in] value
     * @return Node *
     */
    Node *insert(const T &value)
    {
        // 此时树是空的，要在根节点处创建一个新的
        if (this->m_root == this->m_nil)
        {
            this->m_root = new Node;
            this->m_root->value = value;
            this->m_root->parent() = this->m_nil;
            this->m_root->lc() = this->m_nil;
            this->m_root->rc() = this->m_nil;
            this->m_root->data = Color::Black;
            return this->m_root;
        }

        // 否则从根节点出发向下，利用比较确定向左还是向右，沿途的节点 size 都加 1
        Node *p = this->m_root;
        Node *pos = this->m_nil; // 记录最终插入位置
        while (true)
        {
            // 向左，遇到叶节点就创建新节点，然后退出循环
            if (this->cmp(value, p->value))
            {
                if (p->lc() != this->m_nil)
                    p = p->lc();
                else
                {
                    p->lc() = new Node;
                    pos = p->lc();
                    break;
                }
            }
            // 向右，遇到叶节点就创建新节点，然后退出循环
            else
            {
                if (p->rc() != this->m_nil)
                    p = p->rc();
                else
                {
                    p->rc() = new Node;
                    pos = p->rc();
                    break;
                }
            }
        }

        // 插入点赋值，设为红节点，不改变黑高
        pos->value = value;
        pos->parent() = p;
        pos->rc() = this->m_nil;
        pos->lc() = this->m_nil;
        pos->data = Color::Red;

        // 调整插入节点
        Node *me = pos;
        Node *father = me->parent();

        // 只有当父节点是红节点才需要调整
        while (father->data == Color::Red)
        {
            // 父节点是左节点的情况
            if (father->parent()->lc() == father)
            {
                Node *uncle = father->parent()->rc();
                // case 1：父节点和叔节点都是红色，说明父节点的父节点是黑节点
                if (uncle->data == Color::Red)
                {
                    father->data = Color::Black;
                    uncle->data = Color::Black;
                    me = father->parent();
                    father = me->parent();
                    me->data = Color::Red;
                }
                // case 2：叔节点是黑色
                else
                {
                    if (father->lc() != me)
                    {
                        left_rotate(father);
                        me = me->lc();
                        father = me->parent();
                    }
                    father->data = Color::Black;
                    father->parent()->data = Color::Red;
                    right_rotate(father->parent());
                }
            }
            else
            {
                Node *uncle = father->parent()->lc();
                // case 1：父节点和叔节点都是红色，说明父节点的父节点是黑节点
                if (uncle->data == Color::Red)
                {
                    father->data = Color::Black;
                    uncle->data = Color::Black;
                    me = father->parent();
                    father = me->parent();
                    me->data = Color::Red;
                }
                // case 2：叔节点是黑色
                else
                {
                    if (father->rc() != me)
                    {
                        right_rotate(father);
                        me = me->rc();
                        father = me->parent();
                    }
                    father->data = Color::Black;
                    father->parent()->data = Color::Red;
                    left_rotate(father->parent());
                }
            }
        }
        // 根节点一定是黑色
        this->m_root->data = Color::Black;

        // 返回插入节点指针
        return pos;
    }

    /**
     * @brief 根据值删除
     *
     * @param[in] value
     * @return true
     * @return false
     */
    bool remove(const T &value) override
    {
        // 找到节点
        Node *p = this->find(value);
        return remove(p);
    }

    /**
     * @brief 根据节点删除
     *
     * @param[in] p
     * @return true
     * @return false
     */
    bool remove(Node *p) override
    {
        if (p == nullptr || p == this->m_nil)
            return false;

        // 检查左右节点
        Node *lp = p->lc();
        Node *rp = p->rc();
        Node *adj = this->m_nil;
        Color origin = p->data;

        // 节点替换，用 v 替换 u 的位置
        auto replace = [&](Node *u, Node *v) {
            if (u == this->m_root)
                this->m_root = v;
            else if (u == u->parent()->lc())
                u->parent()->lc() = v;
            else
                u->parent()->rc() = v;
            v->parent() = u->parent();
        };

        // size 调整
        if (rp == this->m_nil)
        {
            adj = lp;
            // 用 lp 替换 p，替换过程会赋予 adj 父节点
            replace(p, lp);
            delete p;
        }
        else if (lp == this->m_nil)
        {
            adj = rp;
            // 用 rp 替换 p，替换过程会赋予 adj 父节点
            replace(p, rp);
            delete p;
        }
        else
        {
            // 如果有右节点，就选择右边子树中的最小节点作为新节点
            Node *pos = this->min(rp);
            origin = pos->data;
            adj = pos->rc();

            // 如果新节点是右节点，将 adj 父节点设为 pos；此设置针对 nil 节点，当 adj
            // 是 nil，它的父节点的并不确定，需要指定
            if (pos == rp)
                adj->parent() = pos;
            // 如果新节点不是右节点，就连接新的父节点和新的右节点
            else
            {
                replace(pos, pos->rc());
                pos->rc() = rp;
                rp->parent() = pos;
            }
            // 连接新节点和 p 的父节点和 p 的左右节点
            pos->lc() = lp;
            lp->parent() = pos;

            replace(p, pos);
            pos->data = p->data;
            delete p;
        }

        // 如果删除的节点是黑色，就需要调整节点来平衡黑高
        if (origin == Color::Black)
        {
            // 如果 me 是红色，则变为黑色，然后循环；如果 me 是根，同样
            Node *me = adj;
            while (me != this->m_root && me->data == Color::Black)
            {
                // me 是左节点
                if (me == me->parent()->lc())
                {
                    Node *brother = me->parent()->rc();
                    // 如果兄弟是红色，就改成黑色
                    if (brother->data == Color::Red)
                    {
                        me->parent()->data = Color::Red;
                        brother->data = Color::Black;

                        // 此旋转不会改变 nil 的父节点
                        left_rotate(me->parent());
                        brother = me->parent()->rc();
                    }
                    // 如果兄弟和自己都是 nil，此层平衡，me 向上变为父节点
                    if (me == this->m_nil && brother == this->m_nil)
                        me = me->parent();
                    // 如果兄弟的两个孩子都是黑色，就让兄弟是红色，me 向上变为父节点
                    else if (brother->lc()->data == Color::Black && brother->rc()->data == Color::Black)
                    {
                        brother->data = Color::Red;
                        me = me->parent();
                    }
                    else
                    {
                        // 如果兄弟的右节点是黑色，就修改它，让左节点是黑色
                        if (brother->rc()->data == Color::Black)
                        {
                            brother->lc()->data = Color::Black;
                            brother->data = Color::Red;
                            right_rotate(brother);
                            brother = brother->parent();

                            // 此旋转可能改变 nil 的父节点，需要重新赋值
                            me->parent() = brother->parent();
                        }
                        brother->data = me->parent()->data;
                        me->parent()->data = Color::Black;
                        brother->rc()->data = Color::Black;
                        left_rotate(me->parent());
                        me = this->m_root;
                    }
                }
                // 和左节点的情况对称
                else
                {
                    Node *brother = me->parent()->lc();
                    if (brother->data == Color::Red)
                    {
                        me->parent()->data = Color::Red;
                        brother->data = Color::Black;

                        // 此旋转不会改变 nil 的父节点
                        right_rotate(me->parent());
                        brother = me->parent()->lc();
                    }
                    // 如果兄弟和自己都是 nil，此层平衡，me 向上变为父节点
                    if (me == this->m_nil && brother == this->m_nil)
                        me = me->parent();
                    else if (brother->rc()->data == Color::Black && brother->lc()->data == Color::Black)
                    {
                        brother->data = Color::Red;
                        me = me->parent();
                    }
                    else
                    {
                        if (brother->lc()->data == Color::Black)
                        {
                            brother->rc()->data = Color::Black;
                            brother->data = Color::Red;
                            left_rotate(brother);
                            brother = brother->parent();

                            // 此旋转可能改变 nil 的父节点，需要重新赋值
                            me->parent() = brother->parent();
                        }
                        brother->data = me->parent()->data;
                        me->parent()->data = Color::Black;
                        brother->lc()->data = Color::Black;
                        right_rotate(me->parent());
                        me = this->m_root;
                    }
                }
            }
            // 注意最后自己一定是黑色
            me->data = Color::Black;
        }
        return true;
    }

    /**
     * @brief 红黑树绘制函数
     *
     * @return true
     * @return false
     */
    bool draw() const
    {
        // 高度为零，什么都不做
        int h = height();
        if (h == 0)
            return false;

        // 重复绘制空格
        auto repeat = [](int n, const char *Str) {
            while (n-- > 0)
                std::cout << Str;
        };

        // 获得 n 的位数
        auto digit = [](int n) {
            int t = n > 0 ? 0 : 1;
            n = std::abs(n);
            while (n > 10)
            {
                t++;
                n /= 10;
            }
            return t;
        };

        // 查找第 depth 层的 i 号节点，用于绘制树
        auto floor = [&](int depth, int i) {
            Node *p = this->m_root;

            // 获取全局位置
            double left = 0;
            double right = 1 << (depth - 1);
            int floor = 1;
            while (floor != depth && p != this->m_nil)
            {
                if (i < (left + right) / 2)
                {
                    p = p->lc();
                    right = (left + right) / 2;
                }
                else
                {
                    p = p->rc();
                    left = (left + right) / 2;
                }
                floor++;
            }
            return p;
        };

        // 打印第一行
        int blank = (1 << h) - 2;
        repeat(blank, " ");
        std::cout << details::ansiGray << this->m_root->value << details::ansiReset << std::endl;

        // 每行前面的空格数 2^n - 2 个，从第二行开始
        for (int i = 1; i < h; i++)
        {
            const int num = 1 << i;
            int c = num;

            // 暂存这一层的节点，绘制前置空格
            Node **record = new Node *[num];
            blank = (1 << (h - i)) - 2;
            repeat(blank, " ");

            // 输出树枝所在的行
            while (c > 0)
            {
                record[num - c] = floor(i + 1, num - c);
                blank = (1 << (h - i)) - 1;

                // 获得此行元素
                Node *p = record[num - c];
                if (p != this->m_nil)
                {
                    // 输出左端点
                    if (c % 2 == 0)
                    {
                        std::cout << "|";
                        repeat(blank + 1, "-");
                    }
                    // 输出右端点
                    else
                    {
                        // 回退一格，覆盖左端点为 nil 时产生的空格
                        std::cout << "\b-";
                        repeat(blank, "-");
                        std::cout << "|";
                        repeat(2 * blank + 1, " ");
                    }
                }
                // 当此节点为空，就用空格填充
                else if (c > 1)
                {
                    // 左端点
                    if (c % 2 == 0)
                        repeat(blank + 2, " ");
                    else
                        repeat(3 * blank + 2, " ");
                }
                c--;
            }
            // 此层输出完毕
            std::cout << std::endl;

            c = num;
            blank = (1 << (h - i)) - 2;
            int d = 0;
            // 输出节点所在的行
            while (c > 0)
            {
                repeat(blank, " ");
                repeat(d, "\b");
                // 只需要在这里插入节点输出
                if (record[num - c] != this->m_nil)
                {
                    // 将可能的浮点型直接转为整型，便于格式化
                    int intValue = int(record[num - c]->value);
                    Color color = record[num - c]->data;

                    // 输出节点颜色
                    if (color == Color::Black)
                        std::cout << details::ansiGray << intValue << details::ansiReset;
                    else
                        std::cout << details::ansiRed << intValue << details::ansiReset;

                    // 这里要得到该数值的位数
                    d = digit(intValue);
                }
                // 此节点为空，什么都不输出
                else
                {
                    std::cout << " ";
                    d = 0;
                }
                // 相邻间距 2^(n+1) - 1
                blank = (1 << (h - i + 1)) - 1;
                c--;
            }
            // 移除临时记录表
            delete[] record;
            std::cout << std::endl;
        }
        std::cout << std::endl;
        return true;
    }

  private:
    /**
     * @brief 左旋
     *
     * @param[in] node
     */
    void left_rotate(Node *node)
    {
        // 没有右节点就退出
        if (node->rc() == this->m_nil)
            return;

        Node *rc = node->rc();
        rc->parent() = node->parent();

        // 如果恰好是根节点，就重置根节点
        if (node == this->m_root)
            this->m_root = rc;
        else if (node == node->parent()->rc())
            node->parent()->rc() = rc;
        else
            node->parent()->lc() = rc;

        node->rc() = rc->lc();
        rc->lc()->parent() = node;
        rc->lc() = node;
        node->parent() = rc;
    }

    /**
     * @brief 右旋
     *
     * @param[in] node
     */
    void right_rotate(Node *node)
    {
        // 没有左节点就退出
        if (node->lc() == this->m_nil)
            return;

        Node *lc = node->lc();
        lc->parent() = node->parent();

        // 如果恰好是根节点，就重置根节点
        if (node == this->m_root)
            this->m_root = lc;
        else if (node == node->parent()->lc())
            node->parent()->lc() = lc;
        else
            node->parent()->rc() = lc;

        node->lc() = lc->rc();
        lc->rc()->parent() = node;
        lc->rc() = node;
        node->parent() = lc;
    }
};

} // namespace stl

} // namespace xi
